package struct
{
	import flash.utils.Dictionary;

	public class OrderedList
	{
		public var head:Node = new Node(null);
		public var tail:Node = new Node(null);
		public var count:int = 0;
		public var _index:Dictionary = new Dictionary();

		public function OrderedList()
		{
			link(head, tail);
		}				
		
		public function hasContent(v:IComparable):Boolean {
			return _index[v] != null;
		}
		
		public function updateToHead(v:IComparable):void {
			var node:Node = _index[v];
			if (node == null) return;
			var it:Node = node.pre;
			while (it != head && v.compare(it.content as IComparable) < 0) {
				link(it, node.next);
				link(it.pre, node);
				link(node, it);
				it = it.pre;
			}
		}
		
		public function add(v:IComparable):void {
			var node:Node = new Node(v);
			var it:Node = head.next;
			while (it != tail) {
				if ((it.content as IComparable).compare(v) > 0)
					break;
				it = it.next;
			}
			link(it.pre, node);
			link(node, it);			
			count++;			
			_index[v] = node;
		}
		
		public function link(a:Node, b:Node):void {
			a.next = b;
			b.pre = a;
		}
		
		public function unshift():IComparable {
			if (head.next == tail) return null;
			var result:Node = head.next;
			link(head, head.next.next);
			count--;
			delete _index[result.content];
			return result.content as IComparable;
		}
		
		public function print():void {
			var it:Node = head.next;
			while (it != tail) {
				trace("[OrderedList] " + it.content.toString());
				it = it.next;
			}
		}
	}
}